import 单链表.ListNode;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

//TIP To <b>Run</b> code, press <shortcut actionId="Run"/> or
// click the <icon src="AllIcons.Actions.Execute"/> icon in the gutter.
public class Main {
    public int[] productExceptSelf(int[] nums) {
        //不能直接进行整除
        int len = nums.length;
        int[] l = new int[len];
        int[] r = new int[len];
        l[0] = 1;
        // l[i] 表示i之前的数字乘机
        for (int i = 1; i < len; i++) {
            l[i] = l[i - 1] * nums[i - 1];
        }
        r[len - 1] = 1;
        for (int i = len - 2; i >= 0; i--) {
            r[i] = nums[i + 1] * r[i + 1];
        }
        for (int i = 0; i < len; i++) {
            nums[i] = l[i] * r[i];
        }
        return nums;
    }

//    public int minValidStrings(String[] words, String target) {
//        //words
//
//        //
//    }

    public ListNode getIntersectionNode(ListNode headA
            , ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
        }
        return p2;
    }

    public static void main(String[] args) {
        //

    }

    public int reverse(int x) {
        int res = 0;
        while (x != 0) {
            //每次取末尾数字
            int tmp = x % 10;
            //判断是否 大于 最大32位整数
            if (res > 214748364 || (res == 214748364 && tmp > 7)) {
                return 0;
            }
            //判断是否 小于 最小32位整数
            if (res < -214748364 || (res == -214748364 && tmp < -8)) {
                return 0;
            }
            //res 等于res*10+tmp的值
            res = res * 10 + tmp;
            x /= 10;
        }
        return res;
    }

    //两数之和  给一个整数数组nums和一个目标值target。
    public int[] twoSum(int[] nums, int target) {
        // 目标和为target的整数 可以使用双层for循环，但是这个效率太低了,可以借助hashmap
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int cur = target - nums[i]; //计算当前元素和目标元素的差值
            if (map.containsKey(cur)) {
                //map.get(cur)   key是值value是索引
                return new int[]{map.get(cur), i};
            }
            map.put(nums[i], i);
        }
        return new int[0];
    }

    //https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/
    //无重复最长字串
    public int lengthOfLongestSubstring(String s) {
        //滑动窗口解决  最长不重复字串  l和r 如果不包含了r++，否则l++,还需要删除l之前的元素
        int n = s.length();
        int l = 0, r = 0;
        int maxLen = 0;
        Set<Character> set = new HashSet<>();
        while (r < n) {
            char c = s.charAt(r);
            if (!set.contains(c)) {
                set.add(c);
                r++;
                maxLen = Math.max(maxLen, r - l);
            } else {
                //是要删除左边的元素让l++的,并不是要删除 这个时候c和s.charAt(l)并不相等
                set.remove(s.charAt(l)); //删除c为什么不行?
                l++;
            }
        }
        return maxLen;
    }

    //正则表达式匹配
    //https://leetcode.cn/problems/regular-expression-matching/
    public boolean isMatch(String s, String p) {
        //字符串s 和字符串规律p  实现一个. *
        boolean flag =true;
        for (int i = 0; i < s.length(); i++) {
            char c = p.charAt(i);
            if (c == '*') {
                return true;
            } else if (c == '.') {
                continue;
            } else {
                //匹配字符
                if (i >= s.length() || s.charAt(i) != c) {
                  flag = false;
                }
            }
        }
        if (flag==false) {
            return false;
        }
        return true;
    }
}


